//18.四数之和
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution2 {
    //时间复杂度O(N^3) 空间复杂度O(logN)
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> ret = new ArrayList<>();
        //排序
        Arrays.sort(nums);
        int n = nums.length;
        //固定数a
        for(int i = 0;i<n;){
            //三数之和
            //固定数b
            for(int j = i+1;j<n;){
                int left = j+1;
                int right = n-1;
                long aim = (long)target - nums[i]-nums[j];
                while(left < right){
                    int sum = nums[left]+nums[right];
                    if(sum < aim){
                        left++;
                    }else if(sum > aim){
                        right--;
                    }else{
                        //找到四数之和等于target的数
                        ret.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));
                        //缩小查找范围
                        left++;
                        right--;
                        //去重left和right
                        while(left < right && nums[left] == nums[left-1]){
                            left++;
                        }
                        while(left < right && nums[right] == nums[right+1]){
                            right--;
                        }
                    }
                }
                //去重j
                j++;
                while(j < n && nums[j] == nums[j-1]){
                    j++;
                }
            }
            //去重 i
            i++;
            while(i < n && nums[i] == nums[i-1]){
                i++;
            }
        }
        return ret;
    }
}